package me.mingshan.leetcode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * https://leetcode.cn/problems/asteroid-collision/
 *
 * 给定一个整数数组 asteroids，表示在同一行的小行星。数组中小行星的索引表示它们在空间中的相对位置。
 *
 * 对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
 *
 * 找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。
 *
 *
 *
 * 示例 1：
 *
 * 输入：asteroids = [5,10,-5]
 * 输出：[5,10]
 * 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
 * 示例 2：
 *
 * 输入：asteroids = [8,-8]
 * 输出：[]
 * 解释：8 和 -8 碰撞后，两者都发生爆炸。
 * 示例 3：
 *
 * 输入：asteroids = [10,2,-5]
 * 输出：[10]
 * 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
 *
 * @author hanjuntao
 * @date 2025/6/5 0005
 */
public class L_735_asteroid_collision {


    public static void main(String[] args) {
        int[] asteroids = {5, 10, -5};
        System.out.println(Arrays.toString(asteroidCollision2(asteroids)));

        int[] a = {8, -8};
        System.out.println(Arrays.toString(asteroidCollision2(a)));

        int[] b = {10, 2, -5};
        System.out.println(Arrays.toString(asteroidCollision2(b)));
    }

    /**
     * 根据题解，从前往后遍历，找到当前元素，如果当前元素小于0，则判断当前元素是否与前一个元素相撞，从后往前循环
     * 谁被撞，当前索引的值改为0
     *
     * @param asteroids
     * @return
     */
    public static int[] asteroidCollision(int[] asteroids) {
        for (int i = 0; i < asteroids.length; i++) {
            // 找到当前元素，如果当前元素小于0，则判断当前元素是否与前一个元素相撞
           int cur = asteroids[i];
           if (cur < 0) {
               for (int j = i - 1; j >= 0; j--) {
                   int pre = asteroids[j];
                   if (pre > 0) {
                       int absCur =Math.abs(cur);

                       // 如果前的比较大，说明当前小行星被撞掉
                       if (pre > absCur) {
                           asteroids[i] = 0;
                           break;
                       } else if (pre < absCur) {
                           // 如果前面的比较小，前面的被撞掉， 继续往前撞
                           asteroids[j] = 0;
                       } else {
                           // 如果一样大，说明两个小行星都被撞掉
                           asteroids[j] = 0;
                           asteroids[i] = 0;
                           break;
                       }
                   }
               }
           }
        }

        // 删除数组中值为0的元素
        int countZero = 0;
        for (int i = 0; i < asteroids.length; i++) {
            if (asteroids[i] == 0) {
                countZero++;
            }
        }

        int[] result = new int[asteroids.length - countZero];
        int j = 0;
        for (int i = 0; i < asteroids.length; i++) {
            if (asteroids[i] != 0) {
                result[j] = asteroids[i];
                j++;
            }
        }

        return result;
    }

    /**
     * 栈解法
     *
     * 栈里面存放被撞后仍然存在的小行星。
     *
     *
     * @param asteroids
     * @return
     */
    public static int[] asteroidCollision2(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < asteroids.length; i++) {
            int curr = asteroids[i];
            if (stack.isEmpty() || curr > 0) {
                stack.push(curr);
            } else {
                // 准备入栈的小行星是否存在
                boolean currAlive = true;

                // 栈不为空，且当前元素小于0
                while (!stack.isEmpty() && stack.peek() > 0 && currAlive) {
                    Integer prev = stack.peek();
                    int absCurr = Math.abs(curr);

                    // 如果前面的比较大，说明当前小行星被撞掉
                    if (prev > absCurr) {
                        // 小行星没有了
                        currAlive = false;
                    } else if (prev < absCurr) {
                        // 如果前面的比较小，前面的被撞掉， 继续往前撞
                        stack.pop();
                    } else {
                        // 如果一样大，说明两个小行星都被撞掉
                        stack.pop();
                        currAlive = false;
                    }
                }

                // 如果当前元素还存货，则入栈
                if (currAlive) {
                    stack.push(curr);
                }
            }
        }

        if (stack.isEmpty()) {
            return new int[0];
        }

        int[] result = new int[stack.size()];

        for (int i = stack.size() - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }

        return result;
    }
}
